package org.cainiao.algorithm.temp;

import java.util.HashSet;
import java.util.Set;
import java.util.Stack;

/**
 * <br />
 * <p>
 * Author: Cai Niao(wdhlzd@163.com)<br />
 */
public class TempTest1 {

    public static void main(String[] args) {
        System.out.println(test1("()"));
        System.out.println(test1("()[]{}"));
        System.out.println(test1("(]"));
        System.out.println(test1("{([])[]}"));

        System.out.println("===");

        System.out.println(test2("abcabcbb"));
        System.out.println(test2("bbbbb"));
        System.out.println(test2("pwwkew"));

        System.out.println("===");

        System.out.println(test3(new int[][]{{1, 3, 1}, {1, 5, 1}, {4, 2, 1}}));
        System.out.println(test3(new int[][]{{1, 2, 3}, {4, 5, 6}}));
        System.out.println(test3DP(new int[][]{{1, 3, 1}, {1, 5, 1}, {4, 2, 1}}));
        System.out.println(test3DP(new int[][]{{1, 2, 3}, {4, 5, 6}}));
    }

    private static int test3(int[][] grid) {
        int height;
        if (grid == null || (height = grid.length) < 1) {
            return 0;
        }
        return test3(0, 0, grid, height, grid[0].length);
    }

    private static int test3(int startHeightIndex, int startWidthIndex, int[][] grid, int height, int width) {
        if (startHeightIndex == height - 1 && startWidthIndex == width - 1) {
            return grid[startHeightIndex][startWidthIndex];
        }
        if (startHeightIndex == height - 1) {
            // 只能向右
            return grid[startHeightIndex][startWidthIndex] + test3(startHeightIndex, startWidthIndex + 1, grid, height, width);
        }
        if (startWidthIndex == width - 1) {
            // 只能向下
            return grid[startHeightIndex][startWidthIndex] + test3(startHeightIndex + 1, startWidthIndex, grid, height, width);
        }
        // 向下或向右
        return grid[startHeightIndex][startWidthIndex] + Math.min(test3(startHeightIndex, startWidthIndex + 1, grid, height, width),
            test3(startHeightIndex + 1, startWidthIndex, grid, height, width));
    }

    private static int test3DP(int[][] grid) {
        int height;
        if (grid == null || (height = grid.length) < 1) {
            return 0;
        }
        int width = grid[0].length;
        Integer[][] dp = new Integer[height][width];
        int maxHeightIndex = height - 1;
        int maxWidthIndex = width - 1;
        dp[maxHeightIndex][maxWidthIndex] = grid[maxHeightIndex][maxWidthIndex];
        for (int i = maxWidthIndex - 1; i >= 0; i--) {
            dp[maxHeightIndex][i] = grid[maxHeightIndex][i] + dp[maxHeightIndex][i + 1];
        }
        for (int i = maxHeightIndex - 1; i >= 0; i--) {
            dp[i][maxWidthIndex] = grid[i][maxWidthIndex] + dp[i + 1][maxWidthIndex];
        }
        for (int heightIndex = maxHeightIndex - 1; heightIndex >= 0; heightIndex--) {
            for (int widthIndex = maxWidthIndex - 1; widthIndex >= 0; widthIndex--) {
                dp[heightIndex][widthIndex] = grid[heightIndex][widthIndex]
                    + Math.min(dp[heightIndex][widthIndex + 1], dp[heightIndex + 1][widthIndex]);
            }
        }
        return dp[0][0];
    }

    private static int test2(String str) {
        return test2(str.toCharArray());
    }

    private static int test2(char[] chars) {
        int length;
        if (chars == null || (length = chars.length) < 1) {
            return 0;
        }
        int maxSubLength = 0;
        for (int i = 0; i < length; i++) {
            Set<Character> set = new HashSet<>();
            int lastIndex = i;
            for (int j = i; j < length; j++) {
                char c = chars[j];
                if (set.contains(c)) {
                    lastIndex = j - 1;
                    break;
                }
                set.add(c);
            }
            int subLength = lastIndex - i + 1;
            if (subLength > maxSubLength) {
                maxSubLength = subLength;
            }
        }
        return maxSubLength;
    }

    private static boolean test1(String code) {
        if (code == null) {
            return true;
        }
        return test1(code.toCharArray());
    }

    private static boolean test1(char[] operators) {
        Stack<Character> stack = new Stack<>();
        for (char operator : operators) {
            Character right = getRight(operator);
            if (right == null) {
                Character rightOfLastLeft = stack.pop();
                if (!rightOfLastLeft.equals(operator)) {
                    return false;
                }
            } else {
                stack.push(right);
            }
        }
        return true;
    }

    private static Character getRight(char left) {
        switch (left) {
            case '(':
                return ')';
            case '[':
                return ']';
            case '{':
                return '}';
            default:
                return null;
        }
    }
}
